package com.gxc.string;

/**
 * 给定一个字符串str，求最长的回文子序列。注意区分子序列和子串的不同
 *
 * 解法：
 * 1.递归
 * 2.dp
 *
 * dp[i][j] 是 str 在 i...j 上的最长回文子序列长度
 * i<=j  d[i][i] = 1;
 * dp[i-1][j+1] =
 *                  如果str[i-1]==str[j+1], 则 dp[i-1][j+1] = dp[i][j]+2；
 *                  如果str[i-1]!=str[j+1], 则 dp[i-1][j+1] = max(dp[i-1][j], dp[i][j+1]);
 */
public class LongestPalindromeSubsequence {

    public static void main(String[] args) {
        String str = "cabbeaf";
        System.out.println(process(str));
        System.out.println(dp(str));
        System.out.println(dp2(str));
    }

    /**
     * 递归
     * @param str
     * @return
     */
    public static int process(String str) {
        char[] chars = str.toCharArray();
        return recursion(chars, 0, str.length()-1);
    }

    private static int recursion(char[] chars, int i, int j) {
        if (i == j) return 1;
        if (i > j) return 0;

        if (chars[i] == chars[j]) return recursion(chars, i+1, j-1) + 2;
        else {
            return Math.max(recursion(chars, i+1, j), recursion(chars, i, j-1));
        }
    }

    public static int dp(String str) {
        char[] chars = str.toCharArray();
        int l = str.length();
        int[][] dp = new int[l][l];

        int max = 0;
        for (int j = 0; j < l; j++) {
            for (int i = l-1; i >=0; i--) {
                if (i>j) break;

                if (i == j) {
                    dp[i][j] = 1;
                } else if (chars[i] == chars[j]) {
                    if (i+1 <= j-1) dp[i][j] = dp[i + 1][j - 1] + 2;
                    else dp[i][j] = 2;
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
                max = Math.max(dp[i][j], max);
            }
        }
        return max;
    }

    public static int dp2(String str) {
        char[] chars = str.toCharArray();
        int l = str.length();
        int[][] dp = new int[l][l];

        for (int i = 0; i < l; i++) {
            dp[i][i] = 1;
        }

        int tmp;
        for (int i = 1; i < l; i++) {
            tmp = 0;
            for (int j = 0; j + i < l; j++) {
                if (chars[j] == chars[j+i]) {
                    tmp = dp[j+1][j+i-2] + 2;
                } else {
                    tmp = Math.max(dp[j+1][j+i], dp[j][j+i-1]);
                }
                dp[j][j+i] = tmp;
            }
        }
        return dp[0][l-1];
    }


}
